use std::{str, result};

pub fn add_bit_str(s1: &[u8], s2: &[u8]) -> String{
    println!("s1: {:?} s2: {:?}", &s1, &s2);
    let mut i = s1.len() as isize -1;
    let mut j = s2.len() as isize -1;
    let mut carry = 0;
    let mut result = vec![0u8; i.max(j) as usize];

    let zero = '0' as u8;

    while i >=0 || j >= 0 {
        let digit_a = if i >= 0 {s1[i as usize] - zero } else { 0 };
        i -= 1;
        let digit_b = if j >= 0{ s2[j as usize] - zero} else { 0 };
        j -= 1;
        let mut sum = digit_a + digit_b + carry;
        carry = if sum >= 2 { 1 } else { 0};
        sum = if sum >= 2 { sum - 2} else { sum };
        result.push(sum + zero);
    }
    if carry  == 1{
        result.push(1 + zero);
    }
    result.reverse();
    let r = str::from_utf8(&result).unwrap();
    r.to_string()
}

pub fn count_bit(num: u32) -> Vec<u32> {
    let mut result = vec![0; (num+1) as usize];
    for i in 1..=num {
        result[i as usize] = result[ (i & (i-1)) as usize] + 1;
    }
    result
}

pub fn count_bit_2(num: u32) -> Vec<u32> {
    let mut result = vec![0; (num+1) as usize];
    for i in 1..=num {
        result[i as usize] = result[ (i >> 1) as usize] + (i & 1);
    }
    result
}

mod tests {
    use super::*;
    #[test]
    fn test_count_bit() {
        let expect = vec![0,1,1,2,1];
        let v = count_bit(4);
        assert_eq!(v, expect);
    }
}